/**
 * 115.不同的子序列
 */
public class Exerciser3 {
    public int numDistinct(String s, String t) {
        int m = t.length();
        int n = s.length();
        // dp[i][j]: s字符串中[0,j]区间内的所有子序列中，有多少个t字符串[0,i]区间的子串
        int[][] dp = new int[m + 1][n + 1];
        // 初始化: 如果t字符串为空的话，那么我们在s字符串中一定是可以出现t这个空字符串的
        s = " " + s;
        t = " " + t;
        // 所以把t对应的i位置的0初始化为1
        for(int j = 0;j <= n;j++) {
            dp[0][j] = 1;
        }
        for(int i = 1;i <= m;i++) {
            for(int j = 1;j <= n;j++) {
                // 先把要寻找的一方进行固定，再从s的头到尾进行寻找
                if(t.charAt(i) == s.charAt(j)) {
                    // 添加最后相等的位置，或者不添加相等的位置，存在两种结果
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
                }else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }
}
